package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.Queue;

/**
 * Prim算法(延时实现)构造最小生成树
 * 不断寻找权重最小的横切边加入生成树中，最终生成的生成树即为最小生成树。
 * 
 * 空间复杂度O(E)，时间复杂度O(ElogE)
 * @author 付大石
 */
public class LazyPrim {

    public static void main(String[] args) {
        
        UndirectedGraph g = new UndirectedGraph(8);
        g.addEdge(new Edge(4,5,0.35));
        g.addEdge(new Edge(4,7,0.37));
        g.addEdge(new Edge(5,7,0.28));
        g.addEdge(new Edge(0,7,0.16));
        g.addEdge(new Edge(1,5,0.32));
        g.addEdge(new Edge(0,4,0.38));
        g.addEdge(new Edge(2,3,0.17));
        g.addEdge(new Edge(1,7,0.19));
        g.addEdge(new Edge(0,2,0.26));
        g.addEdge(new Edge(1,2,0.36));
        g.addEdge(new Edge(1,3,0.29));
        g.addEdge(new Edge(2,7,0.34));
        g.addEdge(new Edge(6,2,0.40));
        g.addEdge(new Edge(3,6,0.52));
        g.addEdge(new Edge(6,0,0.58));
        g.addEdge(new Edge(6,4,0.93));
        for(Edge edge : new LazyPrim(g).edges()) {
            System.out.println(edge);
        }
    }
    
    private boolean[] marked;
    private Queue<Edge> mst; // 最小生成树
    private MinPQ<Edge> pq;	
	private double weight;

    public LazyPrim(UndirectedGraph g) {

        marked = new boolean[g.v()];
        mst = new LinkedQueue<>();
        pq = new MinPQ<>();
        visit(g, 0);
        while (!pq.isEmpty()) {
            Edge edge = pq.delMin(); // 最小横切边;
            int v = edge.either();
            int w = edge.other(v);
            if (marked[v] && marked[w]) { // 失效的最小横切边
                continue;
            }
            mst.enqueue(edge);
			weight += ede.weight();
            if (!marked[v]) {
                visit(g, v);
            } else {
                visit(g, w);
            }
        }
    }

    /**
     * 将顶点{@param v}加入最小生成树，并将依附于顶点{@param v}的边加入存储
     * 横切边的优先队列中
     * @param g
     * @param v
     */
    private void visit(UndirectedGraph g, int v) {

        marked[v] = true;
        for (Edge edge : g.adj(v)) {
            if (!marked[edge.other(v)]) {
                pq.insert(edge);
            }
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }
	
	public double weight() {
		return weight;
	}
}
